package org.nerve.datamining.graph;

import org.jgrapht.DirectedGraph;
import org.jgrapht.alg.DijkstraShortestPath;
import org.jgrapht.alg.StrongConnectivityInspector;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;

import java.util.Arrays;
import java.util.List;

/**
 * 使用JPraphT的迪杰斯特拉算法
 * org.nerve.datamining.graph
 * Created by zengxm on 12/9/2016.
 */
public class DijkstraWithJGraphT {

	List<String> nodes = Arrays.asList("张三","李四","王五","宋六","赵七");

	protected DirectedGraph<String, DefaultEdge> buildDirectedGraph(){
		DirectedGraph<String, DefaultEdge> graph= new DefaultDirectedGraph<>(DefaultEdge.class);

		if(nodes!=null)
			nodes.forEach(graph::addVertex);

		//增加关系
		graph.addEdge("张三","李四");
		graph.addEdge("张三","王五");
		graph.addEdge("张三","宋六");
		graph.addEdge("王五","李四");
		graph.addEdge("赵七","李四");
		graph.addEdge("李四","赵七");

		return graph;
	}


	public void show(){
		DirectedGraph<String,DefaultEdge> directedGraph = buildDirectedGraph();
		// computes all the strongly connected components of the directed graph
		StrongConnectivityInspector sci =
				new StrongConnectivityInspector(directedGraph);
		List stronglyConnectedSubgraphs = sci.stronglyConnectedSubgraphs();

		// prints the strongly connected components
		System.out.println("Strongly connected components:");
		for (int i = 0; i < stronglyConnectedSubgraphs.size(); i++) {
			System.out.println(stronglyConnectedSubgraphs.get(i));
		}
		System.out.println();

		String from ="张三",to="赵七";

		// Prints the shortest path from vertex i to vertex c. This certainly
		// exists for our particular directed graph.
		System.out.println("Shortest path from i to c:");
		List path =
				DijkstraShortestPath.findPathBetween(directedGraph, from, to);
		System.out.println(path + "\n");

		// Prints the shortest path from vertex c to vertex i. This path does
		// NOT exist for our particular directed graph. Hence the path is
		// empty and the variable "path"; must be null.
		System.out.println("Shortest path from c to i:");
		path = DijkstraShortestPath.findPathBetween(directedGraph, to, from);
		System.out.println(path);
	}

	public static void main(String[] args) {
		DijkstraWithJGraphT jd=new DijkstraWithJGraphT();
		jd.show();
	}
}
